/**
 * 链表
 */
module.exports = class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  // 追加元素
  append(element) {
    const node = new Node(element);
    // 如果 head 为空，则直接把 head 指向新元素
    if (null === this.head) {
      this.head = node;
    } else {
      // 追加到链表末尾
      let pre = this.head;
      while (pre.next) {
        pre = pre.next;
      }
      pre.next = node;
    }
    this.length++;
  }

  // 任意位置插入元素
  insert(position, element) {
    // 判断欲要插入的位置是否不合法
    if (position < 0 || position > this.length) {
      return false;
    }

    // 创建节点
    const node = new Node(element);
    // 如果插入的位置是头部
    if (0 === position) {
      node.next = this.head;
      this.head = node;
    } else {
      // 遍历节点，寻找指定的位置插入
      let currentNode = this.head;
      for (
        let nextNodeLocation = 1;
        currentNode;
        nextNodeLocation++, currentNode = currentNode.next
      ) {
        // 如果遍历到当前节点，要插入的位置等于当前节点的下一个节点位置
        if (position === nextNodeLocation) {
          node.next = currentNode.next;
          currentNode.next = node;
          break;
        }
      }
    }
    this.length++;
    return true;
  }

  // 移除指定位置元素
  removeAt(position) {
    // 判断欲要移除的位置是否不合法
    if (position < 0 || position > this.length) {
      return null;
    }

    let currentNode = this.head;
    // 如果是移除的位置头部
    if (0 === position) {
      this.head = this.head.next;
    } else {
      for (
        let nextNodeLocation = 1;
        currentNode;
        nextNodeLocation++, currentNode = currentNode.next
      ) {
        // 如果遍历到当前节点，要删除的位置等于当前节点的下一个节点位置
        if (position === nextNodeLocation) {
          // 为了保证返回值，是删除的节点
          const toRemoveNode = currentNode.next;
          currentNode.next = currentNode.next.next;
          currentNode = toRemoveNode;
          break;
        }
      }
    }
    this.length--;
    return currentNode.element;
  }

  // 寻找元素下标
  findIndex(element) {
    let currentNode = this.head;
    let index = 0;
    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }
      currentNode = currentNode.next;
      index++;
    }
    return -1;
  }

  // 删除指定元素
  remove(element) {
    const index = this.findIndex(element);
    return this.removeAt(index);
  }

  // 链表是否为空
  isEmpty() {
    return !this.length;
  }

  // 链表大小
  size() {
    return this.length;
  }

  // 转换到字符串
  toString() {
    let currentNode = this.head;
    let string = '';
    while (currentNode) {
      string += `${currentNode.element} `;
      currentNode = currentNode.next;
    }
    return string.trim();
  }
};

/**
 * 节点
 */
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
